package LeetCode刷题.暑假刷的算法;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-07-21 10:04
 * @description: Functions of this class is 搜索插入位置
 **/
public class 搜索插入位置 {
    public static void main(String args[]){
        int nums[]={1,3,5,6};
        System.out.println(searchInsert(nums,7));
    }

    /**
     *
     * @param nums 一组数
     * @param target 要找的数
     * @return 在数组中如果找到了target的话就直接返回去下标
     * 但是要是没有找到的话，就返回target插入到数组中后的一个下标
     * 其实该题也是同样用二分查找去做，但是只需要在函数最后那句找不到就return -1那里改成return left即可
     * 因为数组有序，所以一旦找不到 退出循环后 left所在的位置也是最靠近target所插入的位置，所以left的下标就可以用于是target插入后的下标
     */
    public static int searchInsert(int[] nums, int target) {
        int left=0;
        int right=nums.length-1;
        while (left<=right){
            int mid=(left+right)>>1;
//            mid =left+((right-left)>>1);//该方法偏左 因为要找到第一个 即最小的，所以要偏左
//            mid =right-((right-left)) >> 1;该方法偏右
            //***这样可以防止越界 如果用(left+right)>>1的方法，当left和right都很大时，加起来就可能会越界的
            if(nums[mid]==target){
                return mid;
            }
            else if(nums[mid]<=target){
                left=mid+1;
            }
            else {
                right=mid-1;
            }
        }
        return left;
    }
}